/*-------------------------------------------------------------------------
 *
 * nbtree.h
 *	  postgres btree 访问方法实现的头文件。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/access/nbtree.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef NBTREE_H
#define NBTREE_H

#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "access/tableam.h"
#include "access/xlogreader.h"
#include "catalog/pg_am_d.h"
#include "catalog/pg_index.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/shm_toc.h"

/* BTPageOpaqueData 中有空间存放 16 位的清理周期 ID */
typedef uint16 BTCycleId;



typedef struct BTPageOpaqueData
{
	BlockNumber btpo_prev;		/* 左兄弟，如果是最左侧则为 P_NONE */
	BlockNumber btpo_next;		/* 右兄弟，如果是最右侧则为 P_NONE */
	uint32		btpo_level;		/* 树级别 --- 叶页面为零 */
	uint16		btpo_flags;		/* 标志位，见下文 */
	BTCycleId	btpo_cycleid;	/* 最新分裂的真空周期 ID */
} BTPageOpaqueData;

typedef BTPageOpaqueData *BTPageOpaque;

#define BTPageGetOpaque(page) ((BTPageOpaque) PageGetSpecialPointer(page))

/* 在 btpo_flags 中定义的位 */
#define BTP_LEAF		(1 << 0)	/* 叶页面，即非内部页面 */
#define BTP_ROOT		(1 << 1)	/* 根页面（没有父页面） */
#define BTP_DELETED		(1 << 2)	/* 页面已从树中删除 */
#define BTP_META		(1 << 3)	/* 元页面 */
#define BTP_HALF_DEAD	(1 << 4)	/* 空的，但仍在树中 */
#define BTP_SPLIT_END	(1 << 5)	/* 分裂组的最右页面 */
#define BTP_HAS_GARBAGE (1 << 6)	/* 页面有 LP_DEAD 元组（已弃用） */
#define BTP_INCOMPLETE_SPLIT (1 << 7)	/* 右兄弟的下行链接丢失 */
#define BTP_HAS_FULLXID	(1 << 8)	/* 包含 BTDeletedPageData */

/*
 * 周期 ID 的最大允许值略低于 64K。这是
 * 为了 pg_filedump 和类似工具的方便：我们希望使用
 * 特殊空间的最后 2 个字节作为索引类型指示符，
 * 限制周期 ID 让 btree 可以使用该空间来存储真空周期 ID
 * 同时仍然允许识别索引类型。
 */
#define MAX_BT_CYCLE_ID		0xFF7F


/*
 * 元页面始终是 btree 索引中的第一页。
 * 它的主要目的是指向 btree 根页面的位置。
 * 我们还指向“快速”根，这是真实有效的根；
 * 详见 README 的讨论。
 */

typedef struct BTMetaPageData
{
	uint32		btm_magic;		/* 应包含 BTREE_MAGIC */
	uint32		btm_version;	/* nbtree 版本（始终 <= BTREE_VERSION） */
	BlockNumber btm_root;		/* 当前根位置 */
	uint32		btm_level;		/* 根页面的树级别 */
	BlockNumber btm_fastroot;	/* 当前“快速”根位置 */
	uint32		btm_fastlevel;	/* “快速”根页面的树级别 */
	/* 仅当 btm_version >= BTREE_NOVAC_VERSION 时，剩余字段有效 */

	/* 上次清理期间删除的、不可回收页面的数量 */
	uint32		btm_last_cleanup_num_delpages;
	/* 上次清理期间的堆元组数量（已弃用） */
	float8		btm_last_cleanup_num_heap_tuples;

	bool		btm_allequalimage;	/* 所有列是否都是“相等图像”？ */
} BTMetaPageData;

#define BTPageGetMeta(p) \
	((BTMetaPageData *) PageGetContents(p))

/*
 * 当前的 Btree 版本是 4。这就是您在创建新索引时会获得的版本。
 *
 * Btree 版本 3 在 PostgreSQL v11 中使用。它与版本 4 基本相同，但堆 TID 不在键空间中。重复键的索引元组可以按任何顺序存储。我们继续支持读取和写入 Btree 版本 2 和 3，因此在 pg_upgrade 时不需要立即重新索引。然而，为了获得新的 heapkeyspace 语义，需要进行 REINDEX。
 *
 * 当 btm_allequalimage 字段设置为 true 时，去重是安全的。在版本 3 上安全读取 btm_allequalimage 字段，但只有版本 4 的索引才使用去重。即使在 PostgreSQL v12 上创建的版本 4 索引也需要进行 REINDEX 才能使用去重，因为没有其他方法可以将 btm_allequalimage 设置为 true（pg_upgrade 尚未被教会设置元页面字段）。
 *
 * Btree 版本 2 与版本 3 基本相同。在元页面中有两个在版本 3 中引入的新字段。版本 2 元页面将在第一次插入时自动升级到版本 3。INCLUDE 索引无法使用版本 2。
 */
#define BTREE_METAPAGE	0		/* 第一个页面是元数据 */
#define BTREE_MAGIC		0x053162	/* 元页面中的魔法数字 */
#define BTREE_VERSION	4		/* 当前版本号 */
#define BTREE_MIN_VERSION	2	/* 最小支持版本 */
#define BTREE_NOVAC_VERSION	3	/* 设置所有元字段的版本 */

/*
 * Btree 索引条目的最大大小，包括其元组头。
 *
 * 我们实际上需要能够在每一页上适应三个项目，
 * 所以将任何单一项目限制为每页可用空间的 1/3。
 *
 * 在极少数情况下，_bt_truncate() 需要放大
 * 堆索引元组以为平局打破器堆 TID
 * 属性腾出空间，在这里我们进行了考虑。
 */
#define BTMaxItemSize(page) \
	MAXALIGN_DOWN((PageGetPageSize(page) - \
				   MAXALIGN(SizeOfPageHeaderData + \
							3*sizeof(ItemIdData)  + \
							3*sizeof(ItemPointerData)) - \
				   MAXALIGN(sizeof(BTPageOpaqueData))) / 3)
#define BTMaxItemSizeNoHeapTid(page) \
	MAXALIGN_DOWN((PageGetPageSize(page) - \
				   MAXALIGN(SizeOfPageHeaderData + 3*sizeof(ItemIdData)) - \
				   MAXALIGN(sizeof(BTPageOpaqueData))) / 3)

/*
 * MaxTIDsPerBTreePage 是可以存储在 btree 叶页面上的堆 TIDs 元组数量的上限。
 * 它用于确定每页临时缓冲区的大小。
 *
 * 注意：我们不考虑每个元组的开销以保持
 * 事情简单（该值基于单个堆 TIDs 数组必须包含的元素数量，以填充页面头部和
 * 特殊区域之间的空间）。 结果，这个值略高（即更加保守），
 * 被认为是可以接受的。
 */
#define MaxTIDsPerBTreePage \
	(int) ((BLCKSZ - SizeOfPageHeaderData - sizeof(BTPageOpaqueData)) / \
		   sizeof(ItemPointerData))

/*
 * 叶页面的填充因子默认为 90%，但可以由用户调整。
 * 对于超出叶级别的页面，我们使用固定的 70% 填充因子。
 * 填充因子在索引构建和拆分最右边的页面时应用；
 * 在拆分非最右边页面时，我们尝试均匀划分数据。
 * 当拆分完全填充且只有一个值（重复值）的页面时，
 * 有效的叶页面填充因子为 96%，无论该页面是否为最右边的页面。
 */
#define BTREE_MIN_FILLFACTOR		10
#define BTREE_DEFAULT_FILLFACTOR	90
#define BTREE_NONLEAF_FILLFACTOR	70
#define BTREE_SINGLEVAL_FILLFACTOR	96

/*
 * 一般来说，btree 代码尝试将其关于
 * 页布局的知识本地化到几个例程中。
 * 然而，我们需要一个特殊的值来指示在期望
 * 页面号码的地方“没有页面编号”。 我们可以用零来表示这一点，因为我们从不需要
 * 指向元数据页面的指针。
 */

#define P_NONE			0

/*
 * 宏用于测试页面在其树级别上是否为最左或最右，
 * 以及保持在不透明数据中的其他状态信息。
 */
#define P_LEFTMOST(opaque)		((opaque)->btpo_prev == P_NONE)
#define P_RIGHTMOST(opaque)		((opaque)->btpo_next == P_NONE)
#define P_ISLEAF(opaque)		(((opaque)->btpo_flags & BTP_LEAF) != 0)
#define P_ISROOT(opaque)		(((opaque)->btpo_flags & BTP_ROOT) != 0)
#define P_ISDELETED(opaque)		(((opaque)->btpo_flags & BTP_DELETED) != 0)
#define P_ISMETA(opaque)		(((opaque)->btpo_flags & BTP_META) != 0)
#define P_ISHALFDEAD(opaque)	(((opaque)->btpo_flags & BTP_HALF_DEAD) != 0)
#define P_IGNORE(opaque)		(((opaque)->btpo_flags & (BTP_DELETED|BTP_HALF_DEAD)) != 0)
#define P_HAS_GARBAGE(opaque)	(((opaque)->btpo_flags & BTP_HAS_GARBAGE) != 0)
#define P_INCOMPLETE_SPLIT(opaque)	(((opaque)->btpo_flags & BTP_INCOMPLETE_SPLIT) != 0)
#define P_HAS_FULLXID(opaque)	(((opaque)->btpo_flags & BTP_HAS_FULLXID) != 0)

/*
 * BTDeletedPageData 是已删除页面的页面内容
 */
typedef struct BTDeletedPageData
{
	FullTransactionId safexid;	/* 查看 BTPageIsRecyclable() */
} BTDeletedPageData;

static inline void
BTPageSetDeleted(Page page, FullTransactionId safexid)
{
	BTPageOpaque opaque;
	PageHeader	header;
	BTDeletedPageData *contents;

	opaque = BTPageGetOpaque(page);
	header = ((PageHeader) page);

	opaque->btpo_flags &= ~BTP_HALF_DEAD;
	opaque->btpo_flags |= BTP_DELETED | BTP_HAS_FULLXID;
	header->pd_lower = MAXALIGN(SizeOfPageHeaderData) +
		sizeof(BTDeletedPageData);
	header->pd_upper = header->pd_special;

	/* 在已删除页面中设置 safexid */
	contents = ((BTDeletedPageData *) PageGetContents(page));
	contents->safexid = safexid;
}

static inline FullTransactionId
BTPageGetDeleteXid(Page page)
{
	BTPageOpaque opaque;
	BTDeletedPageData *contents;

	/* 我们只期望在已删除页面中调用 */
	Assert(!PageIsNew(page));
	opaque = BTPageGetOpaque(page);
	Assert(P_ISDELETED(opaque));

	/* pg_upgrade 的已删除页面 -- 现在必须安全删除 */
	if (!P_HAS_FULLXID(opaque))
		return FirstNormalFullTransactionId;

	/* 从已删除页面获取 safexid */
	contents = ((BTDeletedPageData *) PageGetContents(page));
	return contents->safexid;
}

/*
 * 一个现存的页面是否可以回收？
 *
 * 这个函数的存在是为了集中管理哪些已删除页面现在可以
 * 安全地重用。 然而，_bt_pendingfsm_finalize() 重复了一些相同的
 * 逻辑，因为它不直接处理页面 -- 保持两者同步。
 *
 * 注意：PageIsNew() 页面总是安全可回收，但我们无法在
 * 此处处理它们（调用者自己负责该情况）。 调用者可能
 * 还需要针对新页面进行特殊处理。
 */
static inline bool
BTPageIsRecyclable(Page page)
{
	BTPageOpaque opaque;

	Assert(!PageIsNew(page));

	/* 回收只有在页面已删除且 safexid 足够旧时才可以 */
	opaque = BTPageGetOpaque(page);
	if (P_ISDELETED(opaque))
	{
		/*
		 * 页面已被删除，但何时删除？如果它刚被删除，
		 * 扫描可能已经看到了对它的下行链接，并将在稍后读取该页面。
		 * 只要这可以发生，我们就必须将已删除页面保留为
		 * 坟墓碑。
		 *
		 * 因此检查删除的 XID 是否仍然对
		 * 任何人可见。如果不可见，则仍在进行的扫描不可能看到
		 * 它的下行链接，我们可以回收该页面。
		 *
		 * XXX：如果我们有堆关系，我们可以对在非目录关系中
		 * 回收已删除页面更加积极。 目前我们只是
		 * 传递 NULL。这至少简单而一致。
		 */
		return GlobalVisCheckRemovableFullXid(NULL, BTPageGetDeleteXid(page));
	}

	return false;
}

/*
 * BTVacState 和 BTPendingFSM 是在 VACUUM 期间使用的 nbtree.c 私有状态。
 * 它们被导出供 nbtpage.c 中与页面删除相关的代码使用。
 */
typedef struct BTPendingFSM
{
	BlockNumber target;			/* 当前 VACUUM 删除的页面 */
	FullTransactionId safexid;	/* 页面的 BTDeletedPageData.safexid */
} BTPendingFSM;

typedef struct BTVacState
{
	IndexVacuumInfo *info;
	IndexBulkDeleteResult *stats;
	IndexBulkDeleteCallback callback;
	void	   *callback_state;
	BTCycleId	cycleid;
	MemoryContext pagedelcontext;

	/*
	 * _bt_pendingfsm_finalize() 状态
	 */
	int			bufsize;		/* pendingpages 空间（以 # 元素计） */
	int			maxbufsize;		/* 尊重 work_mem 的最大缓冲区大小 */
	BTPendingFSM *pendingpages; /* 每个新删除页面的一个条目 */
	int			npendingpages;	/* 当前有效待处理页面的数量 */
} BTVacState;

/*
 *	Lehman 和 Yao 的算法要求每个非最右侧
 * 页面上都有一个“高键”。高键不是用于访问堆的元组。它是
 * 一个枢轴元组（见下文的“B-Tree 元组格式说明”）。
 * 页面上的高键必须大于或等于页面上出现的任何
 * 其他键。如果我们发现尝试插入一个严格大于高键的
 * 键，我们知道需要向右移动
 * （这只应在页面自我们检查
 * 父页面以来被拆分时发生）。
 *
 *	我们的插入算法保证可以将右兄弟的初始最小键
 * 用作高键。页面一旦创建，只有在页面拆分时
 * 高键才会改变。
 *
 * 在非最右侧页面上，高键位于项目 1，数据项
 * 从项目 2 开始。最右侧页面没有高键，所以我们从
 * 项目 1 开始存储数据项。
 */

#define P_HIKEY				((OffsetNumber) 1)
#define P_FIRSTKEY			((OffsetNumber) 2)
#define P_FIRSTDATAKEY(opaque)	(P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY)


/*
 * B-树元组格式以及键属性和非键属性的说明：
 *
 * INCLUDE B-树索引具有非键属性。这些是可能通过仅索引扫描返回的附加属性，但不会影响索引中项的顺序（正式来说，非键属性不被视为键空间的一部分）。非键属性仅在实际指向堆元组（非支点元组）的叶索引元组中存在。 _bt_check_natts() 强制执行此处描述的规则。
 *
 * 非支点元组格式（普通/非发布变体）：
 *
 *  t_tid | t_info | 键值 | INCLUDE 列，如果有
 *
 * t_tid 指向堆 TID，在 BTREE_VERSION 4 中是一个破局键列。
 *
 * 非支点元组补充支点元组，后者仅有键列。支点元组的唯一目的是表示键空间如何被分隔。一般而言，任何具有多个级别的 B-树索引（即任何不仅由元数据页面和一个单一的叶根页面组成的索引）必须有一些支点元组，因为支点元组用于遍历树。当形成新的支点时，后缀截断可以省略尾随的键列，这使得它们的逻辑值为负无穷。由于 BTREE_VERSION 4 索引将堆 TID 视为尾随键列，以确保所有索引元组在物理上是唯一的，因此有必要在支点元组中表示堆 TID 作为尾随键列，尽管这通常可以像其他任何键列一样被截断掉。（实际上，堆 TID 被省略而不是截断，因为其表示方式与非支点表示方式不同。）
 *
 * 支点元组格式：
 *
 *  t_tid | t_info | 键值 | [堆 TID]
 *
 * 我们通过滥用支点元组的 t_tid 偏移字段来存储支点元组内存在的列数，因为支点元组从不需要存储真实的偏移量（支点元组通常在 t_tid 中存储下行链接）。当 INDEX_ALT_TID_MASK 位被设置时，偏移字段仅存储列/属性的数量，这个数量不包括有时存储在支点元组中的尾随堆 TID 列——这是通过 BT_PIVOT_HEAP_TID_ATTR 的存在来表示的。t_info 中的 INDEX_ALT_TID_MASK 位在 BTREE_VERSION 4 支点元组中始终被设置，因为 BTreeTupleIsPivot() 必须在 heapkeyspace 版本上可靠地工作。
 *
 * 在版本 2 或版本 3 (!heapkeyspace) 索引中，支点元组中可能未设置 INDEX_ALT_TID_MASK。这使得 BTreeTupleIsPivot() 将无法可靠工作。存储的列数隐式地与索引中的列数相同，就像任何非支点元组一样。（存储的列数不应变化，因为在任何 !heapkeyspace 索引内，键列的后缀截断是不安全的。）
 *
 * t_tid 的偏移数值的 12 个最低有效位用于表示支点元组内的键列数量。这留下 4 个状态位（BT_STATUS_OFFSET_MASK 位），这些状态位由所有设置了 INDEX_ALT_TID_MASK 位（在 t_info 中设置）的元组共享，以存储基本的元组元数据。BTreeTupleIsPivot() 和 BTreeTupleIsPosting() 使用 BT_STATUS_OFFSET_MASK 位。
 *
 * 有时非支点元组也使用一种表示方式，将 t_tid 重用来存储元数据而不是 TID。PostgreSQL v13 引入了一种新的非支点元组格式以支持去重：发布列表元组。去重将多个相等的非支点元组合并为一个逻辑等效的、空间高效的表示。发布列表是 ItemPointerData 元素的数组。非支点元组被懒惰地合并在一起形成发布列表元组，发生在我们原本必须拆分叶页面的时刻。
 *
 * 发布元组格式（替代非支点元组表示）：
 *
 *  t_tid | t_info | 键值 | 发布列表（TID 数组）
 *
 * 发布列表元组通过在 t_info 中设置 INDEX_ALT_TID_MASK 状态位以及在 t_tid 的偏移数值中设置 BT_IS_POSTING 状态位来识别。这些标志重新定义了发布元组的 t_tid 的内容，以存储发布列表的位置（而不是块编号），以及元组中存在的堆 TID 的总数（而不是真实的偏移数值）。
 *
 * t_tid 的偏移数值的 12 个最低有效位用于表示元组中存在的堆 TID 的数量，留下 4 个状态位（BT_STATUS_OFFSET_MASK 位）。与任何非支点元组一样，存储的列数总是隐式地等于索引中的列总数（实际上，永远不会存储非键列，因为不支持与 INCLUDE 索引的去重）。
 */
#define INDEX_ALT_TID_MASK			INDEX_AM_RESERVED_BIT

/* 项指针偏移位掩码 */
#define BT_OFFSET_MASK				0x0FFF
#define BT_STATUS_OFFSET_MASK		0xF000
/* BT_STATUS_OFFSET_MASK 状态位 */
#define BT_PIVOT_HEAP_TID_ATTR		0x1000
#define BT_IS_POSTING				0x2000

/*
 * 注意：与 !heapkeyspace 索引一起使用时，BTreeTupleIsPivot() 可能产生假阴性（但不会产生假阳性）
 */
static inline bool
BTreeTupleIsPivot(IndexTuple itup)
{
	if ((itup->t_info & INDEX_ALT_TID_MASK) == 0)
		return false;
	/* 偏移号中缺少 BT_IS_POSTING 表示枢轴元组 */
	if ((ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) & BT_IS_POSTING) != 0)
		return false;

	return true;
}

static inline bool
BTreeTupleIsPosting(IndexTuple itup)
{
	if ((itup->t_info & INDEX_ALT_TID_MASK) == 0)
		return false;
	/* 偏移号中存在 BT_IS_POSTING 表示发布元组 */
	if ((ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) & BT_IS_POSTING) == 0)
		return false;

	return true;
}

static inline void
BTreeTupleSetPosting(IndexTuple itup, uint16 nhtids, int postingoffset)
{
	Assert(nhtids > 1);
	Assert((nhtids & BT_STATUS_OFFSET_MASK) == 0);
	Assert((size_t) postingoffset == MAXALIGN(postingoffset));
	Assert(postingoffset < INDEX_SIZE_MASK);
	Assert(!BTreeTupleIsPivot(itup));

	itup->t_info |= INDEX_ALT_TID_MASK;
	ItemPointerSetOffsetNumber(&itup->t_tid, (nhtids | BT_IS_POSTING));
	ItemPointerSetBlockNumber(&itup->t_tid, postingoffset);
}

static inline uint16
BTreeTupleGetNPosting(IndexTuple posting)
{
	OffsetNumber existing;

	Assert(BTreeTupleIsPosting(posting));

	existing = ItemPointerGetOffsetNumberNoCheck(&posting->t_tid);
	return (existing & BT_OFFSET_MASK);
}

static inline uint32
BTreeTupleGetPostingOffset(IndexTuple posting)
{
	Assert(BTreeTupleIsPosting(posting));

	return ItemPointerGetBlockNumberNoCheck(&posting->t_tid);
}

static inline ItemPointer
BTreeTupleGetPosting(IndexTuple posting)
{
	return (ItemPointer) ((char *) posting +
						  BTreeTupleGetPostingOffset(posting));
}

static inline ItemPointer
BTreeTupleGetPostingN(IndexTuple posting, int n)
{
	return BTreeTupleGetPosting(posting) + n;
}

/*
 * 获取/设置枢轴元组中的下行块号。
 *
 * 注意：无法断言元组是枢轴元组。如果这样做，则 !heapkeyspace 索引会出现假阳性断言失败。
 */
static inline BlockNumber
BTreeTupleGetDownLink(IndexTuple pivot)
{
	return ItemPointerGetBlockNumberNoCheck(&pivot->t_tid);
}

static inline void
BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
{
	ItemPointerSetBlockNumber(&pivot->t_tid, blkno);
}

/*
 * 获取元组中的属性数量。
 *
 * 注意，这不包括隐式的 tiebreaker heap TID 属性（如果有的话）。还要注意，键属性的数量必须在所有 heapkeyspace 枢轴元组中明确表示。
 *
 * 注意：这被定义为宏，而不是内联函数，以避免包含 rel.h。
 */
#define BTreeTupleGetNAtts(itup, rel)	\
	( \
		(BTreeTupleIsPivot(itup)) ? \
		( \
			ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_OFFSET_MASK \
		) \
		: \
		IndexRelationGetNumberOfAttributes(rel) \
	)

/*
 * 设置元组中的键属性数量。
 *
 * heap TID tiebreaker 属性位也可以在这里设置，指示将在元组末尾存储一个 heap TID 值（即使用特殊的枢轴元组表示）。
 */
static inline void
BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
{
	Assert(nkeyatts <= INDEX_MAX_KEYS);
	Assert((nkeyatts & BT_STATUS_OFFSET_MASK) == 0);
	Assert(!heaptid || nkeyatts > 0);
	Assert(!BTreeTupleIsPivot(itup) || nkeyatts == 0);

	itup->t_info |= INDEX_ALT_TID_MASK;

	if (heaptid)
		nkeyatts |= BT_PIVOT_HEAP_TID_ATTR;

	/* BT_IS_POSTING 位在这里故意未设置 */
	ItemPointerSetOffsetNumber(&itup->t_tid, nkeyatts);
	Assert(BTreeTupleIsPivot(itup));
}

/*
 * 从叶页的高键获取/设置“顶层父”链接。用于页面删除。
 *
 * 注意：无法断言元组是枢轴元组。如果这样做，则 !heapkeyspace 索引会出现假阳性断言失败。
 */
static inline BlockNumber
BTreeTupleGetTopParent(IndexTuple leafhikey)
{
	return ItemPointerGetBlockNumberNoCheck(&leafhikey->t_tid);
}

static inline void
BTreeTupleSetTopParent(IndexTuple leafhikey, BlockNumber blkno)
{
	ItemPointerSetBlockNumber(&leafhikey->t_tid, blkno);
	BTreeTupleSetNAtts(leafhikey, 0, false);
}

/*
 * 获取 tiebreaker heap TID 属性（如果有）。
 *
 * 在发布列表元组的情况下，这返回第一个/最低的 heap TID。
 */
static inline ItemPointer
BTreeTupleGetHeapTID(IndexTuple itup)
{
	if (BTreeTupleIsPivot(itup))
	{
		/* 枢轴元组 heap TID 表示？ */
		if ((ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) &
			 BT_PIVOT_HEAP_TID_ATTR) != 0)
			return (ItemPointer) ((char *) itup + IndexTupleSize(itup) -
								  sizeof(ItemPointerData));

		/* Heap TID 属性被截断 */
		return NULL;
	}
	else if (BTreeTupleIsPosting(itup))
		return BTreeTupleGetPosting(itup);

	return &itup->t_tid;
}

/*
 * 获取最大 heap TID 属性，在没有发布列表元组的非枢轴元组情况下，这可能是唯一的 TID。
 *
 * 仅适用于非枢轴元组。
 */
static inline ItemPointer
BTreeTupleGetMaxHeapTID(IndexTuple itup)
{
	Assert(!BTreeTupleIsPivot(itup));

	if (BTreeTupleIsPosting(itup))
	{
		uint16		nposting = BTreeTupleGetNPosting(itup);

		return BTreeTupleGetPostingN(itup, nposting - 1);
	}

	return &itup->t_tid;
}

/*
 * B-树的操作符策略编号已移至 access/stratnum.h，
 * 因为许多地方需要在 ScanKeyInit() 调用中使用它们。
 *
 * 策略编号的选择方式使得我们可以通过减法进行交换，因此：
 */
#define BTCommuteStrategyNumber(strat)	(BTMaxStrategyNumber + 1 - (strat))

/*
 * 当声明一个新的操作符类时，我们要求用户提供一个 amproc 过程 (BTORDER_PROC)，用于确定对于两个键 a 和 b，a < b，a = b，或 a > b。该例程在这三种情况下必须返回 < 0, 0, > 0。
 *
 * 为了促进加速排序，操作符类可以选择提供第二个过程（BTSORTSUPPORT_PROC）。有关详细信息，请参见 src/include/utils/sortsupport.h。
 *
 * 为了支持由“RANGE offset PRECEDING/FOLLOWING”定义的窗口帧，操作符类可以选择提供第三个 amproc 过程 (BTINRANGE_PROC)，而无论它是否提供排序支持。有关详细信息，请参见 doc/src/sgml/btree.sgml。
 *
 * 为了促进 B-树去重，操作符类可以选择提供第“四”个 amproc 过程（BTEQUALIMAGE_PROC）。有关详细信息，请参见 doc/src/sgml/btree.sgml。
 */

#define BTORDER_PROC		1
#define BTSORTSUPPORT_PROC	2
#define BTINRANGE_PROC		3
#define BTEQUALIMAGE_PROC	4
#define BTOPTIONS_PROC		5
#define BTNProcs			5

/*
 * 我们需要能够区分页面的读请求和写请求，以便正确地进行锁定。
 */

#define BT_READ			BUFFER_LOCK_SHARE
#define BT_WRITE		BUFFER_LOCK_EXCLUSIVE

/*
 * BTStackData -- 在我们向下遍历树时，我们将即将遵循的枢轴元组的位置推送到私有堆栈中。如果我们拆分了一个叶子，我们使用这个堆栈向上遍历树并在其父页面的正确位置插入数据。如果父页面拆分时，我们还必须递归地插入到祖父页面中。由于并发的页面拆分和页面删除，我们的私有堆栈可能会变得过时，但它永远不应给我们一个无法挽回的糟糕画面。
 */
typedef struct BTStackData
{
	BlockNumber bts_blkno;
	OffsetNumber bts_offset;
	struct BTStackData *bts_parent;
} BTStackData;

typedef BTStackData *BTStack;


/*
 * BTScanInsertData 是 btree 私有状态，必要时用于找到索引扫描的初始位置或插入新元组——“插入 
 * scankey”（不要与搜索 scankey 混淆）。它用于通过 _bt_search 下降 
 * B-树。
 *
 * heapkeyspace 指示我们是否期望索引中的所有键在物理上都是唯一的，因为堆 TID 被用作破坏平局的属性，并且索引可能在中枢元组中具有截断的键属性。这实际上是索引关系本身的属性（而不是索引扫描）。heapkeyspace 索引是版本 >= 4 的索引。将这保持在近旁是方便的，而不是重复访问元数据页。
 *
 * allequalimage 被设置为指示去重对该索引是安全的。这也是索引关系的属性，而不是索引扫描。
 *
 * anynullkeys 指示在从索引元组构建 scankey 时，是否有任何键的值为 NULL（注意，已经截断的元组键属性将 NULL 设置为占位符键值，这也影响 anynullkeys 的值）。这是对唯一索引非枢轴元组插入的一个便利，通常临时取消设置 scantid，但如果 anynullkeys 为真，则不应取消设置。值通常与非枢轴元组的 HasNulls 位相匹配，但在插入 INCLUDE 索引时可能不匹配（元组头部值受键和非键属性的 NULL 性影响）。
 *
 * 当 nextkey 为 false（通常情况）时，_bt_search 和 _bt_binsrch 将找到第一个 >= scankey 的项。当 nextkey 为 true 时，它们将找到第一个 > scan key 的项。
 *
 * pivotsearch 被调用者设置为 true，调用者希望使用从叶子页面的高键构建的 scankey 重新查找叶子页面。大多数调用者将其设置为 false。
 *
 * scantid 是用作最终破坏平局属性的堆 TID。当索引扫描不需要为特定物理元组找到位置时，它被设置为 NULL。在插入新元组到 heapkeyspace 索引时必须设置，因为树中的每个元组明确属于一个确切的位置（不过它从不与非 heapkeyspace 索引一起设置）。尽管表示方式不同，nbtree 搜索代码仍然将 scantid 视为另一个插入 scankey 属性。
 *
 * scankeys 是一个用于在 scantid 之前比较的用户可见属性的扫描键条目数组。keysz 是数组的大小。在插入期间，必须为每个属性提供一个扫描键，但在开始常规索引扫描时，有些可以省略。该数组用作灵活数组成员，尽管它的大小设计成可以使用栈分配。有关详细信息，请参见 nbtree/README。
 */
typedef struct BTScanInsertData
{
	bool		heapkeyspace;
	bool		allequalimage;
	bool		anynullkeys;
	bool		nextkey;
	bool		pivotsearch;
	ItemPointer scantid;		/* scankeys 的破坏平局者 */
	int			keysz;			/* scankeys 数组的大小 */
	ScanKeyData scankeys[INDEX_MAX_KEYS];	/* 必须最后出现 */
} BTScanInsertData;

typedef BTScanInsertData *BTScanInsert;

/*
 * BTInsertStateData 是插入过程中使用的工作区域。
 *
 * 这个区域在向下遍历树到达新元组可能属于的第一个叶子页面后填充。跟踪当前 
 * 位置以执行唯一性检查，在我们确定要插入哪个确切页面之前。
 *
 * （这应该是 nbtinsert.c 的私有部分，但 _bt_binsrch_insert 也使用它）
 */
typedef struct BTInsertStateData
{
	IndexTuple	itup;			/* 我们要插入的项 */
	Size		itemsz;			/* itup 的大小——应该是 MAXALIGN() 的 */
	BTScanInsert itup_key;		/* 插入 scankey */

	/* 包含我们可能插入 itup 的叶页面的缓冲区 */
	Buffer		buf;

	/*
	 * 当前缓冲区内的范围缓存。仅用于调用 _bt_check_unique 的插入
	 * 操作。有关详细信息，请参见 _bt_binsrch_insert 和
	 * _bt_findinsertloc。
	 */
	bool		bounds_valid;
	OffsetNumber low;
	OffsetNumber stricthigh;

	/*
	 * 如果 _bt_binsrch_insert 找到现有发布列表中的位置，
	 * 则保存列表中的位置。-1 哨兵值表示与
	 * 将其 LP_DEAD 位设置的现有发布列表元组重叠。
	 */
	int			postingoff;
} BTInsertStateData;

typedef BTInsertStateData *BTInsertState;

/*
 * 用于表示在去重过程中待处理元组的状态。
 */
typedef struct BTDedupInterval
{
	OffsetNumber baseoff;
	uint16		nitems;
} BTDedupInterval;

/*
 * BTDedupStateData 是在去重过程中使用的工作区域。
 *
 * 状态信息字段跟踪整个页面去重过程的状态信息。
 * 当前待处理发布列表的状态也在跟踪中。
 *
 * 待处理发布列表由页面中一组连续的相等项组成，
 * 从页面偏移量 'baseoff' 开始。这是新发布列表的
 * “基础”元组的偏移号。'nitems' 是来自页面的
 * 现有项的当前总数，这些项将被合并以生成
 * 一个新的发布列表元组，包括基础元组项。 （现有
 * 项本身可以是发布列表元组或常规非支点元组。）
 *
 * 在处理待处理发布列表时，需要释放的现有元组的总大小
 * 由 'phystupsize' 跟踪。这条信息允许
 * 去重计算每个新发布列表元组的节省空间，
 * 以及整个页面处理过程的节省空间。
 */
typedef struct BTDedupStateData
{
	/* 整个页面处理过程的去重状态信息 */
	bool		deduplicate;	/* 仍在对页面进行去重？ */
	int			nmaxitems;		/* 到目前为止最大的元组数量 */
	Size		maxpostingsize; /* 最终元组大小的限制 */

	/* 关于当前待处理发布列表的基础元组的元数据 */
	IndexTuple	base;			/* 用于形成新的发布列表 */
	OffsetNumber baseoff;		/* 基的页面偏移量 */
	Size		basetupsize;	/* 没有原始发布列表的基大小 */

	/* 有关待处理发布列表的其他元数据 */
	ItemPointer htids;			/* 待处理发布列表中的 Heap TIDs */
	int			nhtids;			/* htids 数组中 Heap TIDs 的数量 */
	int			nitems;			/* 现有元组/行指针的数量 */
	Size		phystupsize;	/* 包括行指针开销 */

	/*
	 * 要用于页面新版本的元组数组。包含每个连续项目组的一个条目。
	 * 注意，不会成为发布列表元组的现有元组未出现在数组中（它们
	 * 在重复删除过程中被隐式视为未更改）。
	 */
	int			nintervals;		/* 数组中当前的区间数量 */
	BTDedupInterval intervals[MaxIndexTuplesPerPage];
} BTDedupStateData;

typedef BTDedupStateData *BTDedupState;

/*
 * BTVacuumPostingData 是表示如何真空（或删除）发布列表元组的状态，
 * 当其某些（虽然不是全部） TID 需要被删除时。
 *
 * 约定是 itup 字段是输入时的原始发布列表元组，
 * palloc() 的最终元组用于覆盖输出时的现有元组。
 */
typedef struct BTVacuumPostingData
{
	/* 将要更新或已更新的元组 */
	IndexTuple	itup;
	OffsetNumber updatedoffset;

	/* 描述 WAL 中最终 itup 需要的状态 */
	uint16		ndeletedtids;
	uint16		deletetids[FLEXIBLE_ARRAY_MEMBER];
} BTVacuumPostingData;

typedef BTVacuumPostingData *BTVacuumPosting;

/*
 * BTScanOpaqueData 是 btree 私有状态，所需进行索引扫描。
 * 这包括预处理的扫描键（有关预处理的详细信息，请参见 _bt_preprocess_keys()），
 * 有关扫描当前位置信息，以及标记位置的信息（如果有的话）。 
 * （我们使用 BTScanPosData 来表示当前和标记位置所需的数据。） 
 * 此外，我们还可以记住一些已知被杀死的索引条目，这些条目必须标记后，
 * 我们才能离开当前页面。
 *
 * 索引扫描一次处理一个页面：我们固定并读取锁定页面，识别页面上的所有匹配项，
 * 并将其保存在 BTScanPosData 中，然后在将项返回给调用者以供处理时释放读取锁。 
 * 这种方法最小化了锁/解锁的流量。 请注意，我们将固定保持在索引页面上，直到调用者完成所有项 
 * （这对于 VACUUM 同步是必要的，请参见 nbtree/README）。 当我们准备转到下一个页面时，
 * 如果调用者告诉我们任何项已被杀死，我们会重新锁定页面以标记它们为已杀死，然后解锁。
 * 最后，我们释放固定，然后按照适当的方向转到下一个页面。
 *
 * 如果我们正在执行索引仅扫描，我们将为每个匹配项保存整个 IndexTuple，
 * 否则仅保存其堆 TID 和偏移量。 IndexTuples 存入单独的工作空间数组；
 * 每个 BTScanPosItem 存储其元组在该数组中的偏移量。 
 * 发布列表元组一次存储一个“基本”元组，允许相同键为每个发布列表元组中的 TID 返回。
 */

typedef struct BTScanPosItem	/* 我们关于每个匹配的记忆 */
{
	ItemPointerData heapTid;	/* 被引用堆项的 TID */
	OffsetNumber indexOffset;	/* 索引项在页面中的位置 */
	LocationIndex tupleOffset;	/* IndexTuple 在工作区的偏移量（如果有的话） */
} BTScanPosItem;

typedef struct BTScanPosData
{
	Buffer		buf;			/* 如果有效，缓存被锁定 */

	XLogRecPtr	lsn;			/* 页被读取时在WAL流中的位置 */
	BlockNumber currPage;		/* items 数组引用的页面 */
	BlockNumber nextPage;		/* 我们扫描此页面时的页面右链接 */

	/*
	 * moreLeft 和 moreRight 跟踪我们认为当前页面左侧和右侧可能存在匹配的
	 * 索引条目。 当 _bt_checkkeys() 返回 continuescan = false 时，我们可以清除
	 * 适当的标志。
	 */
	bool		moreLeft;
	bool		moreRight;

	/*
	 * 如果我们正在执行索引仅扫描，nextTupleOffset 是关联元组存储工作区中的第一个
	 * 空闲位置。
	 */
	int			nextTupleOffset;

	/*
	 * items数组始终按索引顺序排序（即，递增的indexoffset）。向后扫描时，从后向前填充数组是方便的，因此我们从最后一个槽开始向下填充。
	 * 因此，我们需要一个first-valid-entry和一个last-valid-entry计数器。
	 * itemIndex是一个指示最后返回给调用者的条目的游标。
	 */
	int			firstItem;		/* items[]中的第一个有效索引 */
	int			lastItem;		/* items[]中的最后一个有效索引 */
	int			itemIndex;		/* items[]中的当前索引 */

	BTScanPosItem items[MaxTIDsPerBTreePage];	/* 必须是最后一个 */
} BTScanPosData;

typedef BTScanPosData *BTScanPos;

#define BTScanPosIsPinned(scanpos) \
( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
				!BufferIsValid((scanpos).buf)), \
	BufferIsValid((scanpos).buf) \
)
#define BTScanPosUnpin(scanpos) \
	do { \
		ReleaseBuffer((scanpos).buf); \
		(scanpos).buf = InvalidBuffer; \
	} while (0)
#define BTScanPosUnpinIfPinned(scanpos) \
	do { \
		if (BTScanPosIsPinned(scanpos)) \
			BTScanPosUnpin(scanpos); \
	} while (0)

#define BTScanPosIsValid(scanpos) \
( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
				!BufferIsValid((scanpos).buf)), \
	BlockNumberIsValid((scanpos).currPage) \
)
#define BTScanPosInvalidate(scanpos) \
	do { \
		(scanpos).currPage = InvalidBlockNumber; \
		(scanpos).nextPage = InvalidBlockNumber; \
		(scanpos).buf = InvalidBuffer; \
		(scanpos).lsn = InvalidXLogRecPtr; \
		(scanpos).nextTupleOffset = 0; \
	} while (0)

/* 我们需要为每个等式类型的 SK_SEARCHARRAY 扫描键准备一个 */
typedef struct BTArrayKeyInfo
{
	int			scan_key;		/* 关联键在 arrayKeyData 中的索引 */
	int			cur_elem;		/* elem_values 中当前元素的索引 */
	int			mark_elem;		/* elem_values 中标记元素的索引 */
	int			num_elems;		/* 当前数组值中的元素数量 */
	Datum	   *elem_values;	/* num_elems Datums 的数组 */
} BTArrayKeyInfo;

typedef struct BTScanOpaqueData
{
	/* 所有字段（除了 arraysStarted）由 _bt_preprocess_keys() 设置： */
	bool		qual_ok;		/* 如果条件永远无法满足，则为false */
	bool		arraysStarted;	/* 已启动数组键，但尚未“超出所有数组的结尾”？ */
	int			numberOfKeys;	/* 预处理的扫描键数量 */
	ScanKey		keyData;		/* 预处理的扫描键数组 */

	/* SK_SEARCHARRAY 支持的工作区 */
	ScanKey		arrayKeyData;	/* scan->keyData 的修改副本 */
	int			numArrayKeys;	/* 等式类型数组键的数量（如果有任何无法满足的数组键，则为 -1） */
	int			arrayKeyCount;	/* 表示处理的数组扫描键的数量 */
	BTArrayKeyInfo *arrayKeys;	/* 有关每个等式类型数组键的信息 */
	MemoryContext arrayContext; /* 数组数据的扫描生命周期上下文 */

	/* 被删除项的信息，如果有的话 (killedItems 为 NULL 如果从未使用) */
	int		   *killedItems;	/* currPos.items 被杀死项的索引 */
	int			numKilled;		/* 当前存储项的数量 */

	/*
	 * 如果我们正在执行索引仅扫描，这些是 currPos 和 markPos 的元组存储
	 * 工作区。 每个大小为 BLCKSZ，以便可以容纳尽可能多的完整页面元组。
	 */
	char	   *currTuples;		/* currPos 的元组存储 */
	char	   *markTuples;		/* markPos 的元组存储 */

	/*
	 * 如果标记位置与当前位置在同一页面上，我们不使用 markPos，
	 * 而只需将标记的 itemIndex 保存在 markItemIndex 中 
	 * （currPos 的其他部分对于标记位置有效）。 因此，要确定是否有标记，
	 * 首先查看 markItemIndex，然后查看 markPos。
	 */
	int			markItemIndex;	/* itemIndex，或 -1 如果无效 */

	/* 为了效率将这些放在结构的最后 */
	BTScanPosData currPos;		/* 当前位置信息 */
	BTScanPosData markPos;		/* 标记位置（如果有的话） */
} BTScanOpaqueData;

typedef BTScanOpaqueData *BTScanOpaque;

/*
 * 我们在预处理的扫描键中使用一些私有 sk_flags 位。 我们被允许使用位 16-31 
 * （见 skey.h）。 最上面的位是从索引的 indoption[] 数组条目复制的，
 * 用于索引属性。
 */
#define SK_BT_REQFWD	0x00010000	/* 继续向前扫描所需 */
#define SK_BT_REQBKWD	0x00020000	/* 继续向后扫描所需 */
#define SK_BT_INDOPTION_SHIFT  24	/* 必须清除上述位 */
#define SK_BT_DESC			(INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)
#define SK_BT_NULLS_FIRST	(INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

typedef struct BTOptions
{
	int32		varlena_header_;	/* varlena 头部（请勿直接触摸！） */
	int			fillfactor;		/* 页面填充因子百分比（0..100） */
	float8		vacuum_cleanup_index_scale_factor;	/* 已弃用 */
	bool		deduplicate_items;	/* 尝试去重项？ */
} BTOptions;

#define BTGetFillFactor(relation) \
	(AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
				 relation->rd_rel->relam == BTREE_AM_OID), \
	 (relation)->rd_options ? \
	 ((BTOptions *) (relation)->rd_options)->fillfactor : \
	 BTREE_DEFAULT_FILLFACTOR)
#define BTGetTargetPageFreeSpace(relation) \
	(BLCKSZ * (100 - BTGetFillFactor(relation)) / 100)
#define BTGetDeduplicateItems(relation) \
	(AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
				 relation->rd_rel->relam == BTREE_AM_OID), \
	((relation)->rd_options ? \
	 ((BTOptions *) (relation)->rd_options)->deduplicate_items : true))

/*
 * 进度报告的常量定义。阶段编号必须与
 * btbuildphasename 匹配。
 */
/* PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE 为 1（见 progress.h） */
#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN		2
#define PROGRESS_BTREE_PHASE_PERFORMSORT_1				3
#define PROGRESS_BTREE_PHASE_PERFORMSORT_2				4
#define PROGRESS_BTREE_PHASE_LEAF_LOAD					5

/*
 * btree 的外部入口点，在 nbtree.c 中
 */
extern void btbuildempty(Relation index);
extern bool btinsert(Relation rel, Datum *values, bool *isnull,
					 ItemPointer ht_ctid, Relation heapRel,
					 IndexUniqueCheck checkUnique,
					 bool indexUnchanged,
					 struct IndexInfo *indexInfo);
extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
extern Size btestimateparallelscan(void);
extern void btinitparallelscan(void *target);
extern bool btgettuple(IndexScanDesc scan, ScanDirection dir);
extern int64 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
extern void btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
					 ScanKey orderbys, int norderbys);
extern void btparallelrescan(IndexScanDesc scan);
extern void btendscan(IndexScanDesc scan);
extern void btmarkpos(IndexScanDesc scan);
extern void btrestrpos(IndexScanDesc scan);
extern IndexBulkDeleteResult *btbulkdelete(IndexVacuumInfo *info,
										   IndexBulkDeleteResult *stats,
										   IndexBulkDeleteCallback callback,
										   void *callback_state);
extern IndexBulkDeleteResult *btvacuumcleanup(IndexVacuumInfo *info,
											  IndexBulkDeleteResult *stats);
extern bool btcanreturn(Relation index, int attno);

/*
 * nbtree.c 中内部函数的原型
 */
extern bool _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno);
extern void _bt_parallel_release(IndexScanDesc scan, BlockNumber scan_page);
extern void _bt_parallel_done(IndexScanDesc scan);
extern void _bt_parallel_advance_array_keys(IndexScanDesc scan);

/*
 * nbtdedup.c 中函数的原型
 */
extern void _bt_dedup_pass(Relation rel, Buffer buf, Relation heapRel,
						   IndexTuple newitem, Size newitemsz,
						   bool bottomupdedup);
extern bool _bt_bottomupdel_pass(Relation rel, Buffer buf, Relation heapRel,
								 Size newitemsz);
extern void _bt_dedup_start_pending(BTDedupState state, IndexTuple base,
									OffsetNumber baseoff);
extern bool _bt_dedup_save_htid(BTDedupState state, IndexTuple itup);
extern Size _bt_dedup_finish_pending(Page newpage, BTDedupState state);
extern IndexTuple _bt_form_posting(IndexTuple base, ItemPointer htids,
								   int nhtids);
extern void _bt_update_posting(BTVacuumPosting vacposting);
extern IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting,
								   int postingoff);

/*
 * nbtinsert.c 中函数的原型
 */
extern bool _bt_doinsert(Relation rel, IndexTuple itup,
						 IndexUniqueCheck checkUnique, bool indexUnchanged,
						 Relation heapRel);
extern void _bt_finish_split(Relation rel, Buffer lbuf, BTStack stack);
extern Buffer _bt_getstackbuf(Relation rel, BTStack stack, BlockNumber child);

/*
 * nbtsplitloc.c 中函数的原型
 */
extern OffsetNumber _bt_findsplitloc(Relation rel, Page origpage,
									 OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem,
									 bool *newitemonleft);

/*
 * nbtpage.c 中函数的原型
 */
extern void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level,
							 bool allequalimage);
extern bool _bt_vacuum_needs_cleanup(Relation rel);
extern void _bt_set_cleanup_info(Relation rel, BlockNumber num_delpages);
extern void _bt_upgrademetapage(Page page);
extern Buffer _bt_getroot(Relation rel, int access);
extern Buffer _bt_gettrueroot(Relation rel);
extern int	_bt_getrootheight(Relation rel);
extern void _bt_metaversion(Relation rel, bool *heapkeyspace,
							bool *allequalimage);
extern void _bt_checkpage(Relation rel, Buffer buf);
extern Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access);
extern Buffer _bt_relandgetbuf(Relation rel, Buffer obuf,
							   BlockNumber blkno, int access);
extern void _bt_relbuf(Relation rel, Buffer buf);
extern void _bt_lockbuf(Relation rel, Buffer buf, int access);
extern void _bt_unlockbuf(Relation rel, Buffer buf);
extern bool _bt_conditionallockbuf(Relation rel, Buffer buf);
extern void _bt_upgradelockbufcleanup(Relation rel, Buffer buf);
extern void _bt_pageinit(Page page, Size size);
extern void _bt_delitems_vacuum(Relation rel, Buffer buf,
								OffsetNumber *deletable, int ndeletable,
								BTVacuumPosting *updatable, int nupdatable);
extern void _bt_delitems_delete_check(Relation rel, Buffer buf,
									  Relation heapRel,
									  TM_IndexDeleteOp *delstate);
extern void _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate);
extern void _bt_pendingfsm_init(Relation rel, BTVacState *vstate,
								bool cleanuponly);
extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate);

/*
 * nbtsearch.c 中函数的原型
 */
extern BTStack _bt_search(Relation rel, BTScanInsert key, Buffer *bufP,
						  int access, Snapshot snapshot);
extern Buffer _bt_moveright(Relation rel, BTScanInsert key, Buffer buf,
							bool forupdate, BTStack stack, int access, Snapshot snapshot);
extern OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate);
extern int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum);
extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
extern bool _bt_next(IndexScanDesc scan, ScanDirection dir);
extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost,
							   Snapshot snapshot);

/*
 * nbtutils.c 中函数的原型
 */
extern BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup);
extern void _bt_freestack(BTStack stack);
extern void _bt_preprocess_array_keys(IndexScanDesc scan);
extern void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir);
extern bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir);
extern void _bt_mark_array_keys(IndexScanDesc scan);
extern void _bt_restore_array_keys(IndexScanDesc scan);
extern void _bt_preprocess_keys(IndexScanDesc scan);
extern bool _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
						  int tupnatts, ScanDirection dir, bool *continuescan);
extern void _bt_killitems(IndexScanDesc scan);
extern BTCycleId _bt_vacuum_cycleid(Relation rel);
extern BTCycleId _bt_start_vacuum(Relation rel);
extern void _bt_end_vacuum(Relation rel);
extern void _bt_end_vacuum_callback(int code, Datum arg);
extern Size BTreeShmemSize(void);
extern void BTreeShmemInit(void);
extern bytea *btoptions(Datum reloptions, bool validate);
extern bool btproperty(Oid index_oid, int attno,
					   IndexAMProperty prop, const char *propname,
					   bool *res, bool *isnull);
extern char *btbuildphasename(int64 phasenum);
extern IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft,
							   IndexTuple firstright, BTScanInsert itup_key);
extern int	_bt_keep_natts_fast(Relation rel, IndexTuple lastleft,
								IndexTuple firstright);
extern bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page,
							OffsetNumber offnum);
extern void _bt_check_third_page(Relation rel, Relation heap,
								 bool needheaptidspace, Page page, IndexTuple newtup);
extern bool _bt_allequalimage(Relation rel, bool debugmessage);

/*
 * nbtvalidate.c 中函数的原型
 */
extern bool btvalidate(Oid opclassoid);
extern void btadjustmembers(Oid opfamilyoid,
							Oid opclassoid,
							List *operators,
							List *functions);

/*
 * nbtsort.c 中函数的原型
 */
extern IndexBuildResult *btbuild(Relation heap, Relation index,
								 struct IndexInfo *indexInfo);
extern void _bt_parallel_build_main(dsm_segment *seg, shm_toc *toc);

#endif							/* NBTREE_H */
